/*
909. 蛇梯棋
https://leetcode.cn/problems/snakes-and-ladders/description/
中等 2024/12/04
*/

class Solution {
public:

    // pair<int, int> id2rc(int id, int n) {
    //     int r = (id - 1) / n, c = (id - 1) % n;
    //     if (r % 2 == 1) {
    //         c = n - 1 - c;
    //     }
    //     return {n - 1 - r, c};
    // }

    // 难点：根据1-n*n的ID，转为符合要求的下标：整体从下到上，奇数行从左到右，偶数行从右到左
    pair<int, int> test(int id, int n) {
        // 先算行数：(id-1)/n向下取整是从下往上的行数（0，1，，）
        // 对应的从上往下的行idx是：（n-1）- （id-1）/n
        
        int i1 = (id - 1) / n, i = (n - 1) - i1;
        // (13-1)/6=2(从0行开始)  (18-1)/6=2
        // 此时(6-1)-2=3(第三行)   (6-1)-2=3(第三行)
        

        // 计算列：要考虑是奇数行，还是偶数行
        // 奇数行：id从左往右放，所以列索引是（id-1）% n
        // 偶数行：id从右往左放，所以列索引是（n-1）- (id-1) % n
        int j;
        if (i1 % 2 == 0) { // 为什么是0？i1是奇数行的下标
            j = (id - 1) % n;
        } else {
            j = (n - 1) - ((id - 1) % n);
        }
        // 2%2==0 即 j=(13-1)%6==0
        // 算10
        // 1%2==1 即 (6-1)-((10-1)%6)=2
        return {i,j};

        // 放到一起对比一下，是不是有一些规律性（便于记忆）
        // 从下往上行idx: (id-1)/n  从上往下行idx：(n-1) - (id-1)/n
        // 从左向右列idx：(id-1)%n  从右向左列idx：(n-1) - (id-1)%n  //
        // 只有符号/和%的差别哦
    }

    int snakesAndLadders(vector<vector<int>>& board) {
        int n = board.size();
        vector<int> visit(n * n + 1);
        if (n == 2)
            return 1;
        queue<pair<int, int>> qe;
        qe.emplace(1, 0);//位置以及移动步数
        while (!qe.empty()) {
            auto p = qe.front();
            qe.pop();
            for (int i = 1; i <= 6; ++i) {
                int id = p.first + i;
                if (id > n * n) // 超出边界
                    break;
                auto it = test(id, n);   //得到下一步的行列(二维坐标)
                //使用test函数使k对应的值变为二维数组的坐标
                if (board[it.first][it.second] > 0) { // 存在蛇或梯子
                    id = board[it.first][it.second];
                }
                if (id == n * n) // 到达终点
                    return p.second + 1;
                if (!visit[id]) {
                    visit[id] = true;
                    qe.emplace(id, p.second + 1); // 扩展新状态
                }
            }
        }
        return -1;
    }
};